
#include"DList.h"
/**
 * Definition for singly-linked list.*/
//struct ListNode 
//{
//      int val;
//      struct ListNode *next;
// };
//typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) 
{
    ListNode* fast, * slow, * meet;
    meet = NULL;
    fast = slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            meet = slow;
            break;
        }
    }
    if (fast == NULL || fast->next == NULL)
        return NULL;
    slow = head;
    while (slow != meet)
    {
        slow = slow->next;
        meet = meet->next;
    }
    return slow;
}

void test1()
{
    ListNode* phead = ListCreate();
    /*ListPushBack(phead, 1);
    ListPushBack(phead, 2);
    ListPushBack(phead, 3);
    ListPushBack(phead, 4);
    ListPrint(phead);
    ListPopBack(phead);
    ListPrint(phead);
    ListPopBack(phead);
    ListPrint(phead);
    ListPopBack(phead);
    ListPrint(phead);
    */
    ListPushFront(phead, 1);
    ListPushFront(phead, 2);
    ListPushFront(phead, 3);
    ListPushFront(phead, 4);
    ListPrint(phead);
    int i = 0;
    for (i = 1; i <= 4; i++)
    {
        ListPrint(phead);
        ListNode* ret = ListFind(phead, i);
        ListInsert(ret, 88);
    }
    ListPrint(phead);
    ListDestory(phead);
}
//*Definition for a Node.
typedef struct Node 
{
    int val;
    struct Node* next;
    struct Node* random;
    
}Node;


struct Node* copyRandomList(struct Node* head) 
{
    if (head == NULL)
        return head;
    Node* cur = head;
    while (cur)
    {
        Node* next = cur->next;
        Node* copy = (Node*)malloc(sizeof(Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    cur = head;
    while (cur!=NULL)
    {
        Node* copy = cur->next;
        if (cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;
        if (cur == NULL || cur->next == NULL || cur->next->next == NULL)
            break;
        cur = cur->next->next;
    }
    cur = head;
    Node* ret = NULL;
    while (cur)
    {
        if (ret == NULL)
        {
            ret = cur->next;
        }
        Node* tail = cur->next;
        Node* curNext = tail->next;
        cur->next = tail->next;
        if (curNext)
            tail->next = curNext->next;
        cur = curNext;
    }
    return ret;  
}
int main()
{
    test1();
	return 0;
}